package com.example.bitoperation;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
 * 进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 *
 * 示例 1：
 * 输入：nums = [2,2,3,2]
 * 输出：3
 *
 * 示例 2：
 * 输入：nums = [0,1,0,1,0,1,99]
 * 输出：99
 */
public class Leetcode137_SingleNumberII {
    public static void main(String[] args) {
        int[] num = {0, 1, 0, 1, 0, 1, 99};
        System.out.println(new Solution().singleNumber(num));
    }

    static class Solution {
        /**
         * 逐位求结果的二进制
         * 只有一个数出现一次(将其称为【结果】)
         * 【结果】的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。
         * 对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个0 或 3 个 1，
         * 无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。
         * 所以结果的第 i 个二进制位为 数组中所有元素的第 i 个二进制位之和除以 3 的余数
         * @param nums
         * @return
         */
        public int singleNumber(int[] nums) {
            int res = 0;
            for (int i = 0; i < 32; i++) {
                // 写法一：stream写法
                // int finalI = i;
                // int tmpBitTotal = Arrays.stream(nums)
                //         .map(num -> num >> finalI & 1)
                //         .sum();
                // 写法二
                int tmpBitTotal = 0;
                for (int num : nums) {
                    tmpBitTotal += num >> i & 1;
                }
                if (tmpBitTotal % 3 != 0)
                    res |= (1 << i);

            }
            return res;
        }
    }
}
